In a conventional technique employed as a method of diagnosing deterioration of an exhaust gas purification apparatus disposed in an exhaust passage of an internal combustion engine, an amount (an oxygen storage capacity) of oxygen that can be occluded to the exhaust gas purification apparatus is determined from a difference between an oxygen concentration of exhaust gas flowing into the exhaust gas purification apparatus and an oxygen concentration of exhaust gas flowing out of the exhaust gas purification apparatus after an air-fuel ratio of the exhaust gas flowing into the exhaust gas purification apparatus is modified from a lean air-fuel ratio that is higher than the stoichiometric air-fuel ratio to a rich air-fuel ratio that is lower than the stoichiometric air-fuel ratio, and deterioration of the exhaust gas purification apparatus is diagnosed on the basis of the oxygen storage capacity (see Patent Document 1, for example).